UVa/10841 - Lift hopping in the real world/10841.cpp

   1 #include <sstream>
   2 #include <queue>
   3 #include <iostream>
   4 #include <vector>
   5
   6 using namespace std;
   7
   8 struct edge{
   9   int to, weight, lift;
  10   edge(int t, int w, int l) : to(t), weight(w), lift(l) {}
  11   bool operator < (const edge &that) const{
  12     return weight > that.weight;
  13   }
  14 };
  15
  16 int main(){
  17   int n, k;
  18   while (cin >> n >> k){
  19     vector<edge> g[100];
  20     vector<int> floors[n]; //List of floors visited by elevator i-th
  21     int t[n];
  22     for (int i=0; i<n; ++i){
  23       cin >> t[i];
  24     }
  25     string line;
  26     getline(cin, line);
  27     for (int i=0; i<n; ++i){
  28       getline(cin, line);
  29       stringstream ss(line);
  30       int x, y;
  31       ss >> x;
  32       floors[i].push_back(x);
  33       while (ss >> y){
  34         floors[i].push_back(y);
  35         g[x].push_back(edge(y, (y-x)*t[i], i));
  36         g[y].push_back(edge(x, (y-x)*t[i], i));
  37         x = y;
  38       }
  39     }
  40
  41     int d[100][n];
  42     for (int i=0; i<100; ++i) for (int j=0; j<n; ++j) d[i][j] = INT_MAX;
  43
  44     priority_queue<edge> q;
  45
  46     for (int j=0; j<n; ++j){
  47       if (floors[j].front() == 0){
  48         //cout << "Starting at elevator " << j << " ends at floor " << floors[j].back() << endl;
  49         d[0][j] = floors[j].back() * t[j];
  50         q.push(edge(0, d[0][j], j));
  51       }
  52     }
  53
  54     if (k == 0){
  55       cout << "0" << endl;
  56       continue;
  57     }
  58
  59     while (q.size()){
  60       edge top = q.top(); q.pop();
  61
  62       if (top.to == k) break;
  63       if (d[top.to][top.lift] < top.weight) continue;
  64
  65       for (int i=0; i<g[top.to].size(); ++i){
  66         edge u = g[top.to][i];
  67
  68         int tmp;
  69         if ((tmp = top.weight + u.weight + (top.lift != u.lift?(max(top.to - floors[u.lift].front(), floors[u.lift].back() - top.to)*t[u.lift]+5):0)) < d[u.to][u.lift]){
  70           d[u.to][u.lift] = tmp;
  71           q.push(edge(u.to, tmp, u.lift));
  72         }
  73       }
  74     }
  75     int a = *min_element(d[k], d[k]+n);
  76     if (a < INT_MAX)
  77       cout << a << endl;
  78     else
  79       cout << "IMPOSSIBLE" << endl;
  80
  81
  82   }
  83   return 0;
  84 }